In mathematics, Neville's algorithm is an algorithm used for

polynomial interpolation In numerical analysis, polynomial interpolation is the interpolation of a given data set by the polynomial of lowest possible degree that passes through the points of the dataset. Given a set of data points (x_0,y_0), \ldots, (x_n,y_n), with no ...

that was derived by the mathematician

Eric Harold Neville Eric Harold Neville, known as E. H. Neville (1 January 1889 London, England – 22 August 1961 Reading, Berkshire, England) was an English mathematician. A heavily fictionalised portrayal of his life is rendered in the 2007 novel ''The Indian ...

in 1934. Given ''n'' + 1 points, there is a unique polynomial of degree ''≤ n'' which goes through the given points. Neville's algorithm evaluates this polynomial. Neville's algorithm is based on the Newton form of the interpolating polynomial and the recursion relation for the

divided differences In mathematics, divided differences is an algorithm, historically used for computing tables of logarithms and trigonometric functions. Charles Babbage's difference engine, an early mechanical calculator, was designed to use this algorithm in its o ...

. It is similar to Aitken's algorithm (named after Alexander Aitken), which is nowadays not used.

The algorithm

Given a set of ''n''+1 data points (''x''_''i'', ''y''_''i'') where no two ''x''_''i'' are the same, the interpolating polynomial is the polynomial ''p'' of degree at most ''n'' with the property :''p''(''x''_''i'') = ''y''_''i'' for all ''i'' = 0,…,''n'' This polynomial exists and it is unique. Neville's algorithm evaluates the polynomial at some point ''x''. Let ''p''_''i'',''j'' denote the polynomial of degree ''j'' − ''i'' which goes through the points (''x''_''k'', ''y''_''k'') for ''k'' = ''i'', ''i'' + 1, …, ''j''. The ''p''_''i'',''j'' satisfy the recurrence relation : This recurrence can calculate ''p''_0,''n''(''x''), which is the value being sought. This is Neville's algorithm. For instance, for ''n'' = 4, one can use the recurrence to fill the triangular tableau below from the left to the right. : This process yields ''p''_0,4(''x''), the value of the polynomial going through the ''n'' + 1 data points (''x''_''i'', ''y''_''i'') at the point ''x''. This algorithm needs O(''n''²) floating point operations to interpolate a single point, and O(''n''³) floating point operations to interpolate a polynomial of degree n. The derivative of the polynomial can be obtained in the same manner, i.e: :

Application to numerical differentiation

Lyness and Moler showed in 1966 that using undetermined coefficients for the polynomials in Neville's algorithm, one can compute the Maclaurin expansion of the final interpolating polynomial, which yields numerical approximations for the derivatives of the function at the origin. While "this process requires more arithmetic operations than is required in finite difference methods", "the choice of points for function evaluation is not restricted in any way". They also show that their method can be applied directly to the solution of linear systems of the Vandermonde type.

References

* (link is bad) * J. N. Lyness and C.B. Moler, Van Der Monde Systems and Numerical Differentiation, Numerische Mathematik 8 (1966) 458-464 (doi
10.1007/BF02166671
* Neville, E.H.: Iterative interpolation. J. Indian Math. Soc.20, 87–120 (1934)

External links

*{{MathWorld, title=Neville's Algorithm, urlname=NevillesAlgorithm Polynomials Interpolation de:Polynominterpolation#Algorithmus von Neville-Aitken